package puzzle.projecteuler.p100;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.net.URL;
import java.net.URLDecoder;
import java.util.HashSet;
import java.util.Set;

public class Problem083C {

	private static Integer size = 80;
	
	/**
	 * 考虑最一般的情形，计算一点到其他所有点的最短路径
	 * 
	 * 使用Dijkstra算法。 参考http://blog.programfan.com/article.asp?id=6243
	 *  
	 * 此处与Problem082唯一的区别是方法 {@link #m(int, int, int[])}
	 * 
	 * @param args
	 */
	public static void main(String[] args) throws IOException {
		
		long s = System.currentTimeMillis();
		int[] datas = readData();

		int src = 0;
		long[] d = min(src, datas);
		int des = size*size-1;
		long m = d[des]+datas[src];

		System.out.println(m);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	public static int left(int i) {
		return ((i-1)%size<size-1)?i-1:-1;
	}
	
	public static int right(int i) {
		return ((i+1)%size>0)?i+1:-1;
	}
	
	public static int up(int i) {
		return (i/size>=1)?i-size:-1;
	}

	public static int down(int i) {
		return (i/size<=size-1)?i+size:-1;
	}
	
	public static int m(int i, int j, int[] datas) {
		if (j == left(i) || j == right(i) || j == up(i) || j == down(i)) {
			return datas[j];
		} else {
			return Integer.MAX_VALUE;
		}
	}
	/**
	 * 计算从s到其他所有点的的最小路径长度。
	 * 
	 * 使用Dijkstra算法
	 *  
	 * @param i
	 * @param j
	 * @return
	 */
	public static long[] min(int s, int[] datas) {
		
		//init
		Set<Integer> T = new HashSet<Integer>();
		for (int i = 0; i < datas.length; i ++) {
			if (i != s) {
				T.add(i);
			}
		}
		Set<Integer> S = new HashSet<Integer>();
		S.add(s);
		
		long[] D = new long[datas.length];
		for (int i = 0; i < datas.length; i ++) {
			D[i] = m(s, i, datas);
		}
		//go!!!
		while (!T.isEmpty()) {
			int k = -1;
			for (Integer t: T) {
				if (k == -1) {
					k = t;
				} else {
					if (D[t] < D[k]) k = t;
				}
			}
			T.remove(k);
			S.add(k);
			for (Integer t: T) {
				if (D[t] > D[k] + m(k, t, datas)) {
					D[t] = D[k] + m(k, t, datas);
				}
			}
		}
		return D;
	}

	public static int[] readData() throws IOException {

		URL url = Problem083C.class.getResource("Problem083.txt");
		File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));

		int[] datas = new int[size*size];
		BufferedReader br = new BufferedReader(new FileReader(file));
		String line = null;
		int r = 0;
		while ((line = br.readLine()) != null) {
			String[] tmp = line.split(",");
			for (int c = 0; c < tmp.length; c ++) {
				datas[r*size + c] = Integer.valueOf(tmp[c]);
			}
			r ++;
		}
		br.close();
		return datas;
	}
}
